package 力扣.回溯;

import java.util.ArrayList;
import java.util.List;

public class 组合总和39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
       List<List<Integer>> ans = new ArrayList<>();
       List<Integer> box = new ArrayList<>();
       backTrace(candidates,0,0,target,ans,box);
       return ans;
    }

    private void backTrace(int[] candidates, int i,int teSum,int target, List<List<Integer>> ans, List<Integer> box) {
        final int N = candidates.length;
        if (teSum == target && !box.isEmpty()){
            ans.add(new ArrayList<>(box));
        }
        if (teSum >= target || i >= N){
            return;
        }
        for (int j = i; j < N; j++) {
            int t= candidates[j];
            box.add(t);
            teSum += t;
            backTrace(candidates, j,teSum, target, ans, box);
            box.remove(box.size() - 1);
            teSum -= t;
        }
    }
//回溯法
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
         if (candidates == null || candidates.length == 0){
             return new ArrayList<>();
         }
         List<List<Integer>> ans = new ArrayList<>();
         List<Integer> box = new ArrayList<>();
         backTrace2(candidates,0,target,0,ans,box);
         return ans;
    }

    private void backTrace2(int[] candidates, int i, int target,int sum, List<List<Integer>> ans, List<Integer> box) {
        if (sum == target && !box.isEmpty() ){
            ans.add(new ArrayList<>(box));
        }
        final  int N = candidates.length;
        if (sum >= target){//限制
            return;
        }
        for (int j = i; j < N; j++) {
            box.add(candidates[j]);
            sum += candidates[j];
            backTrace2(candidates, j, target, sum,ans,box);
            box.remove(box.size() - 1);
            sum -= candidates[j];
        }
    }
    //区间dp法
//    public List<List<Integer>> combinationSum3(int[] candidates, int target) {
//        if (candidates== null || candidates.length == 0){
//            return new ArrayList<>();
//        }
//        final  int N = candidates.length;
//        int[] dp = new int[target + 1];
//        for (int x:candidates) {
//            for (int i = x; i <= target ; i++) {
//
//            }
//        }
//    }

    public List<List<Integer>> combinationSum3(int[] candidates, int target) {
           if (candidates == null || candidates.length == 0){
               return new ArrayList<>();
           }
           List<List<Integer>> ans = new ArrayList<>();
           List<Integer> box = new ArrayList<>();
           int teSum = 0;
           backTrace3(candidates,0,teSum,target,box,ans);
           return ans;
    }

    private void backTrace3(int[] candidates, int i, int teSum, int target, List<Integer> box, List<List<Integer>> ans) {
        if (!box.isEmpty() && teSum == target){
            ans.add(new ArrayList<>(box));
        }
        if (teSum >= target){
            return;
        }
        final int N = candidates.length;
        for (int j = i; j < N; j++) {
            int te = candidates[j];
            box.add(te);
            teSum += te;
            backTrace3(candidates, j, teSum, target, box, ans);
            teSum -= te;
            box.remove(box.size() - 1);
        }
    }
}
